package com.rr.middle;

import java.util.HashSet;
import java.util.Set;

/**
 * @author zhuangcanrun
 * @Date 2021/11/05/17:56
 * @description
 **/

/*
* https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference/
* */
public class LongestSubsequence {
    //超时解法，O(n*n)
    public int longestSubsequence_bad(int[] arr, int difference) {
        int length = arr.length;
        int ans = 1;
        Set<Integer> hasCheckIndex = new HashSet<Integer>();
        for (int startIndex = 0; startIndex < length-1; startIndex++) {
            if (length - startIndex < ans) {
                break;
            }
            if (!hasCheckIndex.add(startIndex)) {
                continue;
            }
            int tempAns = 1;
            int nextNum = arr[startIndex] + difference;
            for (int i = startIndex + 1; i < length; i++) {
                if (nextNum == arr[i]) {
                    tempAns++;
                    nextNum += difference;
                    hasCheckIndex.add(i);
                }
            }
            ans = Math.max(ans, tempAns);
        }
        return ans;
    }

    //动态规划  O(n)
    public int longestSubsequence(int[] arr, int difference) {
        int ans = 0;
        int[] dp = new int[40001];
        for (int num : arr) {
            dp[num + 20000] = dp[num + 20000 - difference] + 1;
            ans = Math.max(ans, dp[num + 20000]);
        }
        return ans;
    }


}
